package org.totoro.structure.tree;

/**
 * 满二叉树 （Full Binary Tree）
 * <p>
 * https://www.cnblogs.com/idorax/p/6441043.html
 * <p>
 * 国内定义：
 * 1、节点总数量等于 （2 的 d 次方）-1，这这个课是满二叉树
 * <p>
 * 国外定义：
 * 1、如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
 *
 * @author daocr
 * @date 2023/2/14
 */
public class FullBinaryTree<E extends Comparable<E>> extends BinarySearchTree<E> {

    /**
     * 判断是否为满二叉树
     *
     * @param node
     * @return
     */
    boolean isFullBinaryTree(TreeNode<E> node) {

        if (node == null) {
            return true;
        }

        if (node.getLeft() == null && node.getRight() == null) {
            return true;
        }

        if ((node.getLeft() != null) && (node.getRight() != null)) {
            return (isFullBinaryTree(node.getLeft()) && isFullBinaryTree(node.getRight()));
        }

        return false;
    }

    boolean isFullBinaryTree() {
        int maxDepth = calculateMaxDepth(getRoot());

        Double forecastSize = Math.pow(2, maxDepth + 1) - 1;

        return forecastSize.intValue() == getSize();
    }

    public static void main(String[] args) {

        final FullBinaryTree<Integer> fullBinaryTree = new FullBinaryTree<>();

        fullBinaryTree.add(5);

        // right
        fullBinaryTree.add(9);
        fullBinaryTree.add(8);
        fullBinaryTree.add(10);

        // left
        fullBinaryTree.add(2);
        fullBinaryTree.add(1);
        fullBinaryTree.add(3);


        if (fullBinaryTree.isFullBinaryTree()) {
            System.out.println("符合国内满二叉树标准");
        }

        if (fullBinaryTree.isFullBinaryTree(fullBinaryTree.getRoot())) {
            System.out.println("符合国外满二叉树标准");
        }


    }

}
